Dijkstra Algorithm

contents

다익스트라 알고리즘(Dijkstra's algorithm) 은 음수 가중치가 없는 그래프에서 단일 시작점으로부터 다른 모든 노드까지의 최단 경로를 찾는 가장 기초적인 그래프 탐색 알고리즘입니다.

GPS 내비게이션 시스템을 생각해보세요. 당신은 A 지점(출발지)에 있고 B 지점(목적지)으로 가고 싶습니다. 길(간선)마다 길이도 다르고 교통량(가중치)도 다릅니다. 다익스트라 알고리즘은 총 거리나 시간을 최소화하는 경로를 효율적으로 계산합니다.

💡 핵심 아이디어: 탐욕적 탐색 (Greedy Exploration)

다익스트라 알고리즘은 탐욕 알고리즘(Greedy Algorithm) 입니다. 각 단계에서 국소적으로 최적의 선택을 함으로써 전역 최적해를 찾으려 합니다.

철학은 다음과 같습니다.

1. 항상 시작점에서 가장 가까운 방문하지 않은 노드를 먼저 방문합니다.
2. 노드를 방문하면, 그 노드를 거쳐서 이웃 노드로 가는 더 짧은 경로가 있는지 확인합니다.
3. 모든 노드를 방문하거나 목적지에 도달할 때까지 반복합니다.

🏃 알고리즘 단계별 설명

노드(정점)와 가중치 간선이 있는 그래프가 있고, 시작(Source) 노드 S에서 최단 경로를 찾는다고 가정해 봅시다.

1. 초기화

• 거리 테이블: S에서 다른 모든 노드까지의 알려진 최단 거리를 기록할 테이블을 만듭니다.
  • S 자신까지의 거리는 0으로 설정합니다.
  • 다른 모든 노드까지의 거리는 무한대(∞) 로 설정합니다. ("아직 가는 법을 모른다"는 뜻입니다).
• 방문 집합 (Visited Set): 처리가 완료된 노드를 추적합니다. 처음에는 비어 있습니다.
• 우선순위 큐 (Priority Queue): "방문하지 않은 노드 중 거리가 가장 짧은 것은 무엇인가?"를 효율적으로 알려주는 도구입니다. (0, S)를 큐에 넣습니다.

2. 반복 (루프)

처리할 노드가 남아 있는 동안 (또는 우선순위 큐가 비어 있지 않은 동안):

1. 선택: 알려진 거리가 가장 짧은 방문하지 않은 노드를 선택합니다. 이를 "현재 노드"(u)라고 합시다.
2. 방문 표시: u를 방문 집합에 추가합니다. 이제 우리는 u까지의 절대적인 최단 경로를 찾았다고 확신하는 것입니다.
3. 이웃 완화 (Relax Neighbors): u의 모든 이웃(v)을 살펴봅니다. 잠재적인 새로운 거리를 계산합니다.
   • 새로운_거리 = u까지의_거리 + 간선_가중치(u, v)
   • 비교: 새로운_거리가 현재 알려진 v까지의_거리보다 작은가?
   • 업데이트: 만약 그렇다면(YES), v의 거리 테이블을 새로운_거리로 업데이트하고, 우선순위 큐에 v를 추가/업데이트합니다. 이 과정을 완화(Relaxation) 라고 합니다.

3. 종료

목적지 노드가 "방문됨"으로 표시되거나(경로 하나만 필요할 때), 우선순위 큐가 비면(모든 노드로의 경로가 필요할 때) 알고리즘이 멈춥니다.

✍️ 상세 예제

간단한 그래프로 알고리즘을 따라가 보겠습니다.

• 노드: A, B, C, D
• 시작점: A
• 간선:
  • A → B (거리 4)
  • A → C (거리 2)
  • C → B (거리 1)
  • B → D (거리 5)
  • C → D (거리 8)

초기화:

• 거리: A: 0, B: ∞, C: ∞, D: ∞
• 우선순위 큐: [(0, A)]

1단계:

• 큐에서 가장 작은 값 꺼냄: A (거리 0). A를 방문 처리.
• A의 이웃 확인:
  • B: 경로 A→B는 0 + 4 = 4. 4 < ∞인가? 네. B를 4로 업데이트.
  • C: 경로 A→C는 0 + 2 = 2. 2 < ∞인가? 네. C를 2로 업데이트.
• 거리: A: 0, B: 4, C: 2, D: ∞
• 우선순위 큐: [(2, C), (4, B)] (거리순으로 정렬됨!)

2단계:

• 큐에서 가장 작은 값 꺼냄: C (거리 2). C를 방문 처리.
• C의 이웃 확인:
  • B: 간선 C→B는 1. 경로 A→C→B는 2 + 1 = 3. 3 < 4 (현재 B 거리)인가? 네! 지름길을 찾았습니다. B를 3으로 업데이트.
  • D: 간선 C→D는 8. 경로 A→C→D는 2 + 8 = 10. 10 < ∞인가? 네. D를 10으로 업데이트.
• 거리: A: 0, B: 3, C: 2, D: 10
• 우선순위 큐: [(3, B), (10, D)]

3단계:

• 큐에서 가장 작은 값 꺼냄: B (거리 3). B를 방문 처리.
• B의 이웃 확인:
  • D: 간선 B→D는 5. 경로 A→C→B→D는 3 + 5 = 8. 8 < 10 (현재 D 거리)인가? 네! 또 다른 지름길입니다. D를 8로 업데이트.
• 거리: A: 0, B: 3, C: 2, D: 8
• 우선순위 큐: [(8, D)]

4단계:

• D를 꺼냄. 확인할 이웃 없음. 알고리즘 종료.

최종 결과: D까지의 최단 경로는 8입니다. (경로: A → C → B → D).

⚠️ 한계: 음수 간선

이것은 기억해야 할 가장 중요한 세부 사항입니다: 다익스트라 알고리즘은 그래프에 음수 가중치 간선이 있으면 실패합니다.

왜냐구요? 다익스트라는 "탐욕적"이기 때문입니다. 이 알고리즘은 노드가 한번 "방문됨"으로 표시되면, 그 노드까지의 최단 경로는 확정되었다고 가정합니다. 간선을 추가하면 총 거리가 항상 늘어난다고 가정하는 것입니다.

• 만약 가중치가 -10인 간선이 있다면, 더 멀리 돌아가는 것이 실제로는 경로를 더 짧게 만들 수도 있습니다. 다익스트라는 뒤를 돌아보고 이 실수를 고치지 못합니다.
• 해결책: 음수 간선이 있는 그래프의 경우, 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 합니다.

시간 복잡도

효율성은 우선순위 큐에 사용된 데이터 구조에 따라 달라집니다. V는 노드(정점), E는 간선입니다.

1. 단순 배열 사용: $O(V^2)$
   • $E \approx V^2$인 밀집 그래프(dense graph)에서 좋습니다.
2. 이진 힙 (표준 우선순위 큐) 사용: $O(E \log V)$
   • 표준적인 구현 방식입니다. $E$가 $V^2$보다 훨씬 작은 희소 그래프(sparse graph)에서 훨씬 빠릅니다.
3. 피보나치 힙 사용: $O(E + V \log V)$
   • 이론적으로 가장 빠르지만, 구현이 복잡하고 상수 계수가 커서 실제로는 드물게 사용됩니다.

사용 사례

• 지도 서비스 (구글 맵): 위치 간의 가장 빠른 경로 찾기.
• 네트워크 라우팅 프로토콜 (OSPF): 컴퓨터 네트워크를 통해 데이터 패킷이 이동할 최단 경로 결정.
• 소셜 네트워크: 두 사람 사이의 최단 연결 고리 찾기 ("케빈 베이컨의 6단계 법칙").
• IP 라우팅: IP 주소 목적지까지의 최단 경로 찾기.

references